export class GraphAdjMat<T = number> {

    private vertices: T[] = [] //顶点列表，元素代表“顶点值”，索引代表“顶点索引”
    private adjMat: number[][] = []; // 邻接矩阵，行列索引对应“顶点索引”
    constructor(edges: [T, T][]) {
        const tempArr = [...(new Set(edges.flat()))]
        tempArr.forEach((num) => {
            this.addVertex(num)
        })
        edges.forEach(([i, j]) => {
            this.addEdge(i, j)
        })

    }
    /* 获取顶点数量 */
    size(): number {
        return this.vertices.length
    }
    /* 添加顶点 */
    addVertex(val: T): void {
        if (this.vertices.includes(val)) return
        this.vertices.push(val)
        this.adjMat.forEach((arr) => {
            arr.push(0)
        })
        this.adjMat.push(new Array(this.size()).fill(0))
    }
    /* 删除顶点 */
    removeVertex(a: T): void {
        const index = this.vertices.findIndex((item) => item === a)
        if (index < 0) throw `关联的顶点不存在`
        this.vertices.splice(index, 1)
        this.adjMat.splice(index, 1)
        this.adjMat.forEach((arr) => {
            arr.splice(index, 1)
        })
    }
    /* 添加边 */
    // 参数 a, b 对应 vertices 元素
    addEdge(a: T, b: T): void {
        const i = this.vertices.findIndex((item) => item === a)
        const j = this.vertices.findIndex((item) => item === b)
        if (i < 0 || j < 0) throw '关联的顶点不存在'
        this.adjMat[i][j] = 1
        this.adjMat[j][i] = 1
    }

    /* 删除边 */
    // 参数 a, b  对应 vertices 元素
    removeEdge(a: T, b: T): void {
        const i = this.vertices.findIndex((item) => item === a)
        const j = this.vertices.findIndex((item) => item === b)
        if (i < 0 || j < 0) throw '关联的顶点不存在'
        this.adjMat[i][j] = 0
        this.adjMat[j][i] = 0
    }
    /* 打印邻接矩阵 */
    print(): void {
        console.log('顶点列表 = ', this.vertices);
        console.log('===========邻接矩阵======');
        this.adjMat.forEach((arr) => {
            console.log(arr);
        })
    }
}
export class GraphAdjList<T = number> {
    private adjList: Map<T, Set<T>> = new Map();// 邻接表
    constructor(edges: [T, T][]) {
        const tempArr = [...(new Set(edges.flat()))]
        tempArr.forEach((item) => {
            this.addVertex(item)
        })
        edges.forEach(([a, b]) => {
            this.addEdge(a, b)
        })
    }
    /* 获取顶点数量 */
    size(): number {
        return this.adjList.size
    }
    /* 添加顶点 */
    addVertex(a: T): void {
        if (this.adjList.has(a)) return
        this.adjList.set(a, new Set())
    }
    /* 删除顶点 */
    removeVertex(a: T): void {
        if (!this.adjList.has(a)) throw '顶点不存在'
        this.adjList.delete(a)
        for (const list of this.adjList.values()) {
            list.delete(a)
        }
    }
    /* 添加边 */
    // 参数 a, b 对应 vertices 元素
    addEdge(a: T, b: T): void {
        if (!this.adjList.has(a) || !this.adjList.has(b)) throw '顶点不存在'
        const list1 = this.adjList.get(a)
        const list2 = this.adjList.get(b)
        list1.add(b)
        list2.add(a)
    }

    /* 删除边 */
    // 参数 a, b  对应 vertices 元素
    removeEdge(a: T, b: T): void {
        if (!this.adjList.has(a) || !this.adjList.has(b)) throw '顶点不存在'
        const list1 = this.adjList.get(a)
        const list2 = this.adjList.get(b)
        list1.delete(b)
        list2.delete(a)
    }

    getAdjList(): Map<T, Set<T>> {
        return this.adjList
    }
    /* 打印邻接矩阵 */
    print(): void {
        console.log('邻接表 =');
        for (const [key, value] of this.adjList.entries()) {
            const tmp = [];
            for (const vertex of value) {
                tmp.push(vertex);
            }
            console.log(key + ': ' + tmp.join('->'));
        }

    }
}
